package Tree;

import java.util.HashMap;

/**
 * @BelongsProject: SeniorArchitect-LeetCode
 * @BelongsPackage: Tree
 * @Author: zhuangxiaoyan
 * @CreateTime: 2023-10-25  07:24
 * @Description: TODO
 * @Version: 1.0
 */
public class 前序中序构建二叉树105 {

    // 给定的前序和中序遍历构建一个二叉树
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int prelen = preorder.length;
        int inlen = inorder.length;
        if (prelen != inlen) {
            throw new RuntimeException("Imcorrent input data");
        }
        HashMap<Integer, Integer> map = new HashMap<>();
        // 遍历一次中序遍历
        for (int i = 0; i < inlen; i++) {
            map.put(inorder[i], i);
        }
        // 然后递归调用
        return buildTree2(preorder, 0, prelen - 1, map, 0, inlen - 1);
    }

    private TreeNode buildTree2(int[] preorder, int preleft, int preright, HashMap<Integer, Integer> map, int inleft, int inright) {

        // 递归的终止条件
        if (preleft > preright || inleft > inright) {
            return null;
        }
        int rootvalue = preorder[preleft];
        TreeNode root = new TreeNode(rootvalue);
        // 获取标
        int pIndex = map.get(rootvalue);
        root.left = buildTree2(preorder, preleft + 1, pIndex - inleft + preleft, map, inleft, pIndex - 1);
        root.right = buildTree2(preorder, pIndex - inleft + preleft + 1, preright, map, pIndex + 1, inright);
        return root;
    }

    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }
}
